package io.alvin.ch05;

import javax.security.auth.callback.LanguageCallback;
import java.util.Arrays;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 并行Shell排序
 *
 * Created by Alvin on 2017/7/13.
 */
public class ParallelShellSortDemo {

    static int[] arr;
    static ExecutorService pool = Executors.newCachedThreadPool();
    static final int  Thread_Num = 2;
    static AtomicInteger result = new AtomicInteger(-1);

    /**
     * 插入排序
     * @param arr
     */
    public static void insertSort(int[] arr) {
        int length = arr.length;
        int j, i, key;
        for (i = 1; i < length; i++) {
            // key为要准备插入的元素
            key = arr[i];
            j = i-1;
            while (j >= 0 && arr[j] > key) {
                arr[j + i] = arr[j];
                j--;
            }
            //找到合适的位置 插入key
            arr[j + 1] = key;
        }
    }

    /**
     * 希尔排序的串行实现
     * @param arr
     */
    public static void shellSort(int[] arr) {
        // 计算出最大的h值
        int h = 1;
        while (h <= arr.length / 3) {
            h = h * 3 + 1;
        }
        while (h > 0) {
            for (int i = h; i < arr.length; i++) {
                if (arr[i] < arr[i - h]) {
                    int tmp = arr[i];
                    int j = i - h;
                    while (j >= 0 && arr[j] > tmp) {
                        arr[j + h] = arr[j];
                        j -= h;
                    }
                    arr[j + h] = tmp;
                }
            }
            // 计算出下一个h
            h = (h - 1) / 3;
        }
    }

    /**
     * 希尔排序的并行实现
     */
    public static class ShellSortTask implements Runnable {
        int i = 0;
        int h = 0;
        CountDownLatch latch;

        public ShellSortTask(int i, int h, CountDownLatch latch) {
            this.i = i;
            this.h = h;
            this.latch = latch;
        }

        public void run() {
            if (arr[i] < arr[i - h]) {
                int tmp = arr[i];
                int j = i - h;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + h] = arr[j];
                    j -= h;
                }
                arr[j+h] = tmp;
            }
            latch.countDown();
        }
    }

    /**
     * 希尔排序并行实现.
     * 在h>=4时，使用并行线程，否则使用传统的插入排序
     * @param arr
     */
    public static void pShellSort(int[] arr) throws InterruptedException {
        // 计算出最大的h值
        int h = 1;
        CountDownLatch latch = null;
        while (h <= arr.length / 3) {
            h = h * 3 + 1;
        }
        while (h > 0) {
            System.out.println("h=" + h);
            if (h > 4)
                latch = new CountDownLatch(arr.length - h);
            for (int i = h; i < arr.length; i++) {
                // 控制线程数量
                if (h >= 4) {
                    pool.execute(new ShellSortTask(i, h, latch));
                } else {
                    if (arr[i] < arr[i-h]) {
                        int tmp = arr[i];
                        int j = i - h;
                        while (j >= 0 && arr[j] > tmp) {
                            arr[j + h] = arr[j];
                            j -= h;
                        }
                        arr[j + h] = tmp;
                    }
                    System.out.println(Arrays.toString(arr));
                }
            }
            // 等待线程排序完成，进入下一次排序
            latch.await();
            // 计算下一个h值
            h = (h - 1) / 3;
        }
    }
}
